# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 18_min_after_remove_k_digits.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/2/8 11:06
------------------------------------------
    给出一个整数，删除其中的 k个数，使得剩下的数组成的数尽可能小
    1）不能改变元素顺序
    2）所给整数可能超过 Python最大整数的范围
    3）k ≤ 整数长度

    思路：
        1) 删除 k个数字后组成的整数位数相同，就要考虑降低高位数字的大小
        2) 如何降低高位数字大小？把原整数的所有数字从左到右排列(按照原先的先后顺序)，若某一位大于它右边的数字，那么删除该数字之后，
            必然使该数位的值降低，因为右边比它小的数字顶替了它的位置

    本体运用了 [贪心算法]：依次求得局部最优解，最终得到全局最优解的思想
"""


def remove_k_digits(num, k):
    # 新整数的最终长度 = 原整数长度 - k，这里注意理解，是新整数而不是栈的长度，后边要涉及到，注意理解
    new_length = len(num) - k

    # 创建一个栈（Python中用list代替），用于接收所有数字
    stack = []

    for i in range(len(num)):
        # 遍历当前数字
        c = num[i]
        while len(stack) > 0 and stack[-1] > c and k > 0:
            stack.pop()
            k -= 1

        # 如果遇到数字 0，且栈为空， 0不入栈
        if c == '0' and len(stack) == 0:
            # 这个时候，0在最高位，默认去掉

            new_length -= 1
            if new_length <= 0:
                return "0"

            continue

        # 遍历得到的当前数字入栈
        stack.append(c)

    # 找到栈中第一个非零数字位置，以此构建新的整数字符串
    if new_length <= 0:
        return "0"

    return "".join(stack)


def demo():
    """
    out: 120936
    """
    num = "541270936"
    k = 3
    print(remove_k_digits(num, k))


if __name__ == '__main__':
    demo()
